from typing import List


class Solution:
    def trap(self, height: List[int]) -> int:
        left = [height[0]] * len(height)
        right = [height[-1]] * len(height)
        for i in range(1,len(height)):
            left[i] = max(left[i-1],height[i])
        for i in range(len(height)-2,-1,-1):
            right[i] = max(right[i+1],height[i])
        result = 0
        for i in range(len(height)):
            result += max(min(left[i],right[i])-height[i],0)
        return result


if __name__ == '__main__':
    s = Solution()
    r = s.trap([0,1,0,2,1,0,1,3,2,1,2,1])
    print(r)